import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-06-13
 * Time: 9:02
 */
public class Main {
    public static void shiftdown( int [] arr, int root , int end) {
        int parents = root;
        int child = parents*2 + 1 ;
        while( child < end) {
            if( child + 1 <end && arr[child] < arr[child+1]) {
                child++;
            }
            if( arr[child] > arr[parents]) {
                int tmp = arr[child];
                arr[child] = arr[parents];
                arr[parents] = tmp;
                parents = child;
                child = 2*parents + 1;
            } else {
                break;
            }
        }
    }
    public static void createheap(int[]arr,int len) {
        int p;
        for( p = (arr.length-1-1) / 2 ; p>=0 ; p--) {
            shiftdown(arr,p,len);
        }
    }
    public static void heapSort( int []arr) {
        int end = arr.length-1;
        while( end>=0) {
            int tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
            shiftdown(arr,0,end);
            end--;
        }
    }
    public static void main(String[] args) {
        int []arr = {5,45,6,11,22,13,14,19};
        createheap(arr,arr.length);
        System.out.println("排序前"+Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后"+Arrays.toString(arr));
    }
}
